package com.zhuang.search;

import java.util.Arrays;

public class FibonacciSearch {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        System.out.println(fibSearch(arr, 89));
    }

    // 斐波那契数列获取
    public static int[] fib() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    //编写斐波那契查找算法
    /**
     * @param a   数组
     * @param key 我们需要查找的关键码
     * @return 返回对应的下标，如果没有-1
     */
    public static int fibSearch(int[] a, int key) {
        int low = 0;
        int high = a.length - 1;
        // 表示斐波那契分割数值的下标
        int k = 0;
        // 存放mid的值
        int mid = 0;
        int[] f = fib();//获取到斐波那契数列
        // 获取到斐波那契分割数值的下标
        while (high > f[k] - 1) {
            k++;
        }
        // 因为f[k]值可能大于a的长度，需要使用Arrays类，构造一个新的数组，并指a[]
        int[] temp = Arrays.copyOf(a, f[k]);
        // 实际上需求使用a数组最后的数填充temp
        // temp={1,8,10,89,1000,1234,0,0,0} => temp={1,8,10,89,1000,1234,1234,1234,1234}
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = a[high];
        }
        //使用while循环来处理，找到我们的key
        while (low <= high) {
            mid = low + f[k - 1] - 1;
            if (key < temp[mid]) {
                //我们应该向数组的前面查找（左边）
                high = mid - 1;
                /**
                 * 为什么k--
                 *  全部元素=前面的元素+后边的元素
                 *  f[k]=f[k-1]+f[k-2];
                 *  因为前面有f[k-1]个元素，所以可以继续拆分f[k-1]=f[k-2]+f[k-3]
                 *  在f[k-1]的前面继续查找k--;
                 *  下次循环 mid-f[k-1-1]-1
                 */
                k--;
            } else if (key > temp[mid]) {
                //我们应该向数组的后面查找（右边）
                /**
                 * 为什么k-=2
                 * 全部元素=前面的元素+后边的元素
                 * f[k]=f[k-1]+f[k-2];
                 * 因为前面有f[k-2]个元素，所以可以继续拆分f[k-1]=f[k-3]+f[k-4]
                 * 在f[k-2]的前面继续查找k-=2;
                 * 下次循环 mid-f[k-1-2]-1
                 */
                low = mid + 1;
                k -= 2;
            } else {
                //需要确定，返回的是哪个下标
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}
